package com.klun.project.common.constans.leetcode;

import com.klun.project.common.constans.utils.ParseUtils;

import java.util.List;

//给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
// 测试用例的答案是一个 32-位 整数。
// 子数组 是数组的连续子序列。
//
// 示例 1:
//输入: nums = [2,3,-2,4]
//输出: 6
//解释: 子数组 [2,3] 有最大乘积 6。
//
// 示例 2:
//输入: nums = [-2,0,-1]
//输出: 0
//解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

// 示例 3:
//输入: nums = [-2,3,-1]
//输出: 9
//解释: 子数组 [-2,3,-1] 。
//
// 提示:
// 1 <= nums.length <= 2 * 104
// -10 <= nums[i] <= 10
// nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
// Related Topics 数组 动态规划
// 👍 1827 👎 0

public class Solution152 {

	// f(i) ： 含有i的数组最大乘积
	public int maxProduct(int[] nums) {
		int maxF = nums[0], minF = nums[0], ans = nums[0];
		int len = nums.length;
		for (int i = 1; i < len; i++) {
			int mx = maxF, mn = minF;
			maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
			minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
			ans = Math.max(maxF, ans);
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution152 solution = new Solution152();
		List<List<Integer>> arrayLists = ParseUtils.stringToIntLists("[[2],[3,4],[6,5,7],[4,1,8,3]]");
		System.out.println(solution.maxProduct(new int[]{1, 2, 3, 4}));
		System.out.println(solution.maxProduct(new int[]{2, 3, -2, 4}));
	}

}
